package mergesort;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Random;

public class MergeSort {

    static int count = 0;

    /**
     * 对数器验证：思想，用java提供的工具类和我们自己写的算法对处理后的数组，
     * 进行每一个元素比对。
     */
    private static boolean logarithmizer(int[] arr, int[] newArr) {
        /**
         * java提供的工具类
         */
        Arrays.sort(newArr);
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != newArr[i]) {
                count++;
                return false;
            }
        }

        return true;
    }

    @Test
    public void client() {

        Random random = new Random(1);
        for (int i = 0; i < 500; i++) {
            /**
             * 随机样本长度
             */
            int anInt = random.nextInt(100) + 1;
            int[] arr = new int[anInt];
            for (int j = 0; j < anInt; j++) {
                /**
                 * 随机样本数据
                 */
                arr[j] = random.nextInt(100);
            }
            // 定义一个协助原始数组排序的数组
            int[] help = new int[arr.length];
            System.out.println("=======================第" + (i + 1) + "次=======================");
            System.out.println("排序前==》" + Arrays.toString(arr));
            // 归并排序入口
            mergeSort(arr, 0, arr.length - 1, help);
            System.out.println("排序后==》" + Arrays.toString(arr));
            int[] newArr = Arrays.copyOf(arr, arr.length);
            boolean logarithmizer = logarithmizer(arr, newArr);
            if (logarithmizer) {
                System.out.println("对数器验证结果：PASS");
            } else {
                System.out.println("对数器验证结果：NOT PASS");
            }
        }

        System.out.println("==============================================");
        System.out.println("=======                                 ======");
        System.out.println("=======    验证不通过结果为：" + count + "   ======");
        System.out.println("=======                                 ======");
        System.out.println("==============================================");
    }

    public void mergeSort(int[] arr, int left, int right, int[] help) {
        if (left < right) {
            // 找出分治的中间点
            // int mid = left + ((right -left) >> 1);
            int mid = (left + right) / 2;
            // 递归划分右边的区域
            mergeSort(arr, left, mid, help);
            // 递归划分左边的区域
            mergeSort(arr, mid + 1, right, help);
            // 合并已经排序完毕的部分
            merge(arr, left, mid, right, help);
        }
    }

    public void merge(int[] arr, int left, int mid, int right, int[] help) {
        // 标记左半区域第一个未排序的元素，左半区域第一个开始元素就是下标为l的元素
        int l = left;
        // 标记右半区域第一个未排序的元素，右半区域第一个元素就是下标为mid+1的元素
        int r = mid + 1;
        // 定义一个辅助数组的开始下标，和l一样，都是从0开始
        int k = left;
        // 左半区域还有元素并且右半区域也有数据的情况下，
        while (l <= mid && r <= right) {
            // 左半区域第一个没有排序的元素比右半区域第一个没有排序的元素小于等于的情况
            if (arr[l] < arr[r]) {
                // 将左半区域这个没有排序的更小的元素放在辅助数组中，并且标记左半区域第一个未排序的元素的下标右移
                help[k++] = arr[l++];
            } else { // 左半区域第一个没有排序的元素比右半区域第一个没有排序的元素大于的情况
                // 将右半区域这个没有排序的更小的元素放在辅助数组中，并且标记右半区域第一个未排序的元素的下标右移
                help[k++] = arr[r++];
            }
        }

        // 比较完成之后，要么左半区域还有剩余的元素，要么就是右半区域还有剩余的元素，但是不管怎么样，这些元素一定是有序的，直接拷贝即可
        // 左半区域还有剩余的元素
        while (l <= mid) {
            help[k++] = arr[l++];
        }

        // 左半区域还有剩余的元素
        while (r <= right) {
            help[k++] = arr[r++];
        }

        // 将有序的数组拷贝到原始数组中，拷贝过程中直接覆盖原始数组
        while (left <= right) {
            arr[left] = help[left];
            left++;
        }
    }
}
